//	--------------------------------------------------------------------
//	Copyright(C) 2006,2007 Zhao Yukun. All rights reserved.
//	This file is a part of the Xeres system.
//	Xeres 2007
//	Contact : xeres.engine@gmail.com
//	$(reservedInfo)
//	$(reservedDeclaration)
//	--------------------------------------------------------------------
///	@file	<dep_map.h>
///	@path	~/src/lib/utilities/
///	@date	2007/06/17
///	@desc	Dependency map.

#pragma once

#include "xeres.h"

// STL
#include <list>
#include <vector>

#include "lib/utilities/dict.h"
#include "lib/utilities/string.h"

namespace xeres {

	/*!
		\class	dep_map
		\brief	Dependency map. All contents will be sorted in dependency order.
		\details
			Components or executions may have dependency relations, e.g. A depends on B, A should run after B.
			dep_map is designed for solving such order.<BR>
			<BR>
		\eg	Resolve dependency
		\code
			// A sample string dependency map.
			typedef dep_map< AString > StrDepMap;

			StrDepMap map;
			map.add_node( "a" , _S("a") , _S("b;e") );
			map.add_node( "b" , _S("b") , _S("c;d") );
			map.add_node( "c" , _S("c") , _S("e") );
			map.add_node( "d" , _S("d") , _S("c") );
			map.add_node( "e" , _S("e") , _S("") );
			map.add_node( "f" , _S("f") , _S("e;a") );

			StrDepMap::iterator it = map.begin();
			while( it != map.end() )
			{
				printf( "%s" , (*it).c_str() );
				++it;
			}

		\endcode

		\sa	dep_stages
	*/
	template<
		typename _NodeType
	> class dep_map
	{
	public:

		/// \name Constructor & Destructor
		//@{

		/// \ctor
		dep_map( void );

		/// \dtor
		~dep_map( void );

		//@}

		/// \brief Dependency description separator.
		static const wchar_t DEP_SEPARATOR = ';';

		/// \name Node Manipulation
		//@{

		/*!
			\brief		Add node to map & calculate dependency.
			\param[in]		content			Content of node.
			\param[in]		name			Name of node.
			\param[in]		dependency		Node dependency description.
		*/
		void add_node( const _NodeType& content , const WString& name , const WString& dependency );

		//@}

	protected:

		// sort dep
		bool sort_nodes( void );

	private:

		// dependency node internal structure
		struct _Node
		{
			_NodeType			m_content;
			_Node *				m_next;
			const WString *		m_name;
			int					m_visit;
			int					m_id;
			WString				m_dep;

			/// \ctor
			_Node( void );

			// copier
			_Node( const _Node& n );

			// visit tag
			enum { NOT_VISITED , VISITING , VISITED };

			static const int INVALID_NODE_ID = (-INT_MAX);

			// method

			// get next node
			_Node * get_next( void );

			// determine if node is tail
			bool is_tail( void ) const;

			// clear node visit info
			void clear_visit( void );

			// set visit
			void set_visit( bool visting );

			// determine if node is not visited
			bool is_not_visited( void ) const;

			// determine if node is visiting
			bool is_visiting( void ) const;

			// determine if node is visited
			bool is_visited( void ) const;


			// visited guard
			class _NodeVisiteGuard
			{
			public:
				/// \ctor
				_NodeVisiteGuard( _Node& tn );

				/// \dtor
				~_NodeVisiteGuard( void );

			private:
				// holder
				_Node&	m_tn;
			};

		};

		// traversal dependency
		bool traversal_dep( _Node& tn , int& visited );

		// build dependency
		bool build_dep( const WString& dep , std::vector< _Node * >& dep_nodes );

		// insert as root node
		void insert_root( _Node& tn , int visited );

		// insert node after
		void insert_after( _Node& tn , _Node * after_this , int visited );

		// resort all task id
		void resort_id( void );


		// data

		// node map
		typedef dict< WString , _Node > NodeMap;
		NodeMap					m_nodeMap;

		// root node
		_Node *					m_nodeRoot;

	public:

		/// \name Iteration
		//@{

		/// Dependency map iterator.
		struct iterator
		{
		public:

			/// \name Constructors
			//@{

			/// \ctor
			iterator( void );

			/// \ctor_set
			iterator( _Node * node );

			/// \ctor_copy
			iterator( const iterator& rhs );

			//@}

			/// \name Iteration Operators
			//@{

			/// Assignment
			iterator& operator = ( const iterator& rhs );

			/// *
			_NodeType& operator * ( void );

			/// *
			const _NodeType& operator * ( void ) const;

			/// ++ (prefix)
			iterator& operator ++ ( void );

			/// ++ (postfix)
			iterator operator ++ ( int );

			/// ==
			bool operator == ( const iterator& it ) const;

			/// !=
			bool operator != ( const iterator& it ) const;

			//@}

		private:

			_Node *			m_node;
		};

		/// \brief Returns an iterator addressing the first element in dependency map.
		iterator begin( void );

		/// \brief Returns an iterator that addresses the location succeeding the last element in dependency map.
		iterator end( void );

		//@}

	};

} // namespace xeres

#include "lib/utilities/dep_map.inl"
